package master2;

import java.awt.*;
import java.util.*;

/**
 * @author chenyw
 * @date 2022/9/24 21:26
 * 丑数II
 */
public class M264nthUglyNumber {
    //动态规划
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p3 = 1, p2 = 1, p5 =1;
        for (int i = 2; i <= n; i++) {
            int tmp = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            dp[i] = tmp;
            if (tmp == dp[p2] * 2) {
                p2++;
            }
            if (dp[p3] * 3 == tmp) {
                p3++;
            }
            if (dp[p5] * 5 == tmp) {
                p5++;
            }
        }
        return dp[n];
    }


/*    //使用小顶堆
    public int nthUglyNumber(int n) {
        int[] arr = {2, 3, 5};
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        set.add(1L);
        queue.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long poll = queue.poll();
            ugly= (int) poll;
            for (int j = 0; j < 3; j++) {
                long tmp = poll * arr[j];
                if (set.add(tmp)) {
                    queue.offer(tmp);
                }
            }
        }
        return ugly;
    }*/
}
